package com.itheima.datastructure.array;

import java.util.Arrays;

/**
 * 合并两个有序数组 ( Leetcode 88 题改)，将一个数组（此数组有个两个有序部分） 合并到另一个数组中
 */
public class E01Merge2SortedArray {

    public static void main(String[] args) {
        int[] a1 = {1, 5, 6, 2, 4, 10, 11};
        int[] a2 = new int[a1.length];
        mergeRecursion(a1, 0, 2, 3, 6, a2, 0);
        mergeIterator(a1, 0, 2, 3, 6, a2);
        System.out.println(Arrays.toString(a2));
        System.arraycopy(a2, 0, a1, 0, a2.length);
        System.out.println(Arrays.toString(a1));
    }


    /**
     * 循环
     *
     * @param a        原始数组
     * @param oneStart 第一个有序区段的起点
     * @param oneEnd   第一个有序区段的终点
     * @param twoStart 第二个有序区段的起点
     * @param twoEnd   第二个有序区段的终点
     * @param na       结果数组
     */
    public static void mergeIterator(int[] a, int oneStart, int oneEnd, int twoStart, int twoEnd, int[] na) {
        //新数组需要插入的索引
        int nIndex = oneStart;
        while (oneStart <= oneEnd && twoStart <= twoEnd) {
            if (a[oneStart] < a[twoStart]) {//如果区间1的值更小，则将a1[i]赋值给a2[k]
                na[nIndex] = a[oneStart];
                oneStart++;
            } else {
                //否则，将a1[j]赋值给a2[k]
                na[nIndex] = a[twoStart];
                twoStart++;
            }
            nIndex++;
        }
        if (oneStart > oneEnd) {
            //将剩余的区间值复制给a2
            System.arraycopy(a, twoStart, na, nIndex, twoEnd - twoStart + 1);
        }
        if (twoStart > twoEnd) {
            //将剩余的区间值复制给a2
            System.arraycopy(a, oneStart, na, nIndex, oneEnd - oneStart + 1);
        }
    }


    /**
     * 递归
     *
     * @param a        原始数组
     * @param oneStart 第一个有序区间的起点
     * @param oneEnd   第一个有序区间的终点
     * @param twoStart 第二个有序区间的起点
     * @param twoEnd   第二个有序区间的起点终点
     * @param na       结果数组
     * @param nIndex   赋值的索引
     */
    public static void mergeRecursion(int[] a, int oneStart, int oneEnd, int twoStart, int twoEnd,
                                      int[] na, int nIndex) {

        //第一个有序区段已经处理完,则将另一个区间的值复制给结果数组
        if (oneStart > oneEnd) {
            //   src,   srcPos,  dest, destPos,length
            System.arraycopy(a, twoStart, na, nIndex, twoEnd - twoStart + 1);
        }
        if (twoStart > twoEnd) {
            System.arraycopy(a, oneStart, na, nIndex, oneEnd - oneStart + 1);
        }


        if (a[oneStart] < a[twoStart]) {
            //如果区间1的值更小，则将a1[i]赋值给a2[k]
            na[nIndex] = a[oneStart];
            mergeRecursion(a, oneStart + 1, oneEnd, twoStart, twoEnd, na, nIndex + 1);
        } else {
            //否则，将a1[j]赋值给a2[k]
            na[nIndex] = a[twoStart];
            mergeRecursion(a, oneStart, oneEnd, twoStart + 1, twoEnd, na, nIndex + 1);
        }
    }
}
